package com.hdu.other.dp.statusDP;

import java.util.Arrays;
import java.util.List;

public class lc1434 {
    class Solution {

        final int mod = 1000000007;
        public int numberWays(List<List<Integer>> hats) {
            int maxHat = 0;
            for (List<Integer> hat : hats) {
                for (int hatNum : hat) {
                    maxHat = Math.max(maxHat, hatNum);
                }
            }
            int peopleCount = hats.size();
            int status = 0;
            // peopleCount = 4
            // 1111
            int[][] dp = new int[1 << peopleCount][maxHat + 1];
            for (int i = 0; i < 1 << peopleCount; i++) {
                Arrays.fill(dp[i], -1);
            }
            int[] hatInfo = new int[maxHat + 1];
            for (int peopleIndex = 0; peopleIndex < peopleCount; peopleIndex++) {
                List<Integer> curPeopleHatInfo = hats.get(peopleIndex);
                for (int hatNum : curPeopleHatInfo) {
                    hatInfo[hatNum] |= (1 << peopleIndex);
                }
            }
            return f(1, maxHat, status, hatInfo, dp, peopleCount);
        }

        int f(int hatIndex, int maxHat, int status, int[] hatInfo, int[][] dp, int peopleCount) {
            if (status == (1 << peopleCount) - 1) {
                return 1;
            }
            if (hatIndex == maxHat + 1) {
                return 0;
            }
            if (dp[status][hatIndex] != -1) {
                return dp[status][hatIndex];
            }
            int ans = f(hatIndex + 1, maxHat, status, hatInfo, dp, peopleCount);
            int curHatInfo = hatInfo[hatIndex];
            for (int i = 0; i < peopleCount; i++) {
                if ((curHatInfo & (1 << i)) != 0 && (status & (1 << i)) == 0) {
                    int curAns = f(hatIndex + 1, maxHat, status | (1 << i), hatInfo, dp, peopleCount);
                    ans = (ans + curAns) % mod;
                }
            }
            return dp[status][hatIndex] = ans;
        }
    }
}
